import math

def isNumber(value):
    try:
        float(value)
        return True
    except :
        return False

def evaluate(formula):
    unitList=formula2UnitList(formula)
    unitList.append('\0')
    operateStack=['\0']
    numberStack=[]
    index=0
    while len(operateStack)>0:
        unit=unitList[index]
        index=index+1
        if isNumber(unit):
            numberStack.append(float(unit))
        else:
            topOperate=operateStack[len(operateStack)-1]
            if unit==')'or unit=='\0':
                topOperate=operateStack.pop()
                while (unit==')' and topOperate!='(') or (unit=='\0' and topOperate!='\0'):
                    result=handle(numberStack.pop(),numberStack.pop(),topOperate)
                    numberStack.append(result)
                    topOperate=operateStack.pop()

            elif getOperatePriority(topOperate)-getOperatePriority(unit)>=0:
                result=handle(numberStack.pop(),numberStack.pop(), operateStack.pop())
                numberStack.append(result)
                operateStack.append(unit)

            else:
                operateStack.append(unit)
        
    return numberStack

def getPriority(op1,op2):
    if op1=='\0':
        if op2==op1:
            return '='
        return '<'
    if op2=='(':
        return '<'
    if op2=='\0':
        return '>'
    if op2==')':
        if op1=='(':
            return '='
        return '>'
    if getOperatePriority(op2)-getOperatePriority(op1)>0:
        return '<'
    else:
        return '>'

                
def realEvaluate(formule):
    unitList=formula2UnitList(formula)
    unitList.append('\0')
    operateStack=['\0']
    numberStack=[]
    index=0
    while len(operateStack)!=0:
        unit=unitList[index]
        if isNumber(unit):          
            numberStack.append(float(unit))
            index=index+1
        else:
            topOperate=operateStack[len(operateStack)-1]
            priority=getPriority(topOperate,unit)
            if priority == '<':
                operateStack.append(unit)
                index=index+1
            if priority == '=':
                index=index+1
                operateStack.pop()
            if priority == '>':
                if(topOperate=='!'):
                    operateStack.pop()
                    result=factorial(numberStack.pop())
                else:
                    result=handle(numberStack.pop(),numberStack.pop(), operateStack.pop())
                numberStack.append(result)
    return numberStack
    



def handle(value1,value2,operate):
    if operate=='+':
        return value2+value1
    if operate=='-':
        return value2-value1
    if operate=='*' or operate=='x':
        return value2*value1
    if operate=='/':
        return value2/value1
    if operate=='^':
        return math.pow(value2,value1)
    if operate=='!':
        return factorial(value1)
    return 0

def factorial(value2):
    value2=int(value2)
    if value2==0:
        return 1
    result=1
    for i in range(1,value2+1):
        result=result*i
    return result


def getOperatePriority(operate):
    if operate == '+' or operate == '-':
        return 1
    if operate == '*' or operate == 'x' or operate == '/':
        return 2
    if operate == '^':
        return 3
    if operate == '!':
        return 4
    return -1

def formula2UnitList(formula):
    tmp=''
    unitList=[]
    for b in formula:
        if b.isdigit() or b=='.':
            tmp=tmp+b
        else:
            if isNumber(tmp):
                unitList.append(tmp)
            unitList.append(b)
            tmp=''
    if tmp!='':
        unitList.append(tmp)
    return unitList

formula='(4-8)^4'
formula='12+3*25-0.750+2^3+(4-8)^4'
formula='(1+2^3!-4)*(5!-(6-(7-(89-0!))))'
formula='(1+2*6)/(4*5-7)'
print(realEvaluate(formula))


# print('3.6是数字嘛？',isNumber('3f'))
            
        
